Cao Khai Đạo xuất thân từ Thương châu (滄州, nay gần tương ứng với Thương Châu, Hà Bắc). Khi còn niên thiếu, ông nuôi sống bản thân bằng việc đun nước biển lấy muối để bán. Ông được mô tả là dũng mãnh và nhanh nhẹn trên lưng ngựa.

Vào năm 616 hay trước đó, Cao Khai Đạo gia nhập vào đội quân nổi dậy của thủ lĩnh Cách Khiêm (格謙). Cách Khiêm sau đó bị tướng Tùy là Dương Nghĩa Thần giết chết vào năm 616,[1] Cao Khai Đạo thu thập tàn quân của Cách Khiêm. Cao Khai Đạo dẫn quân đi cướp bóc khu vực nay là bắc bộ Hà Bắc.

Năm 617, Cao Khai Đạo cho quân bao vây thành Bắc Bình (北平, nay thuộc Tần Hoàng Đảo, Hà Bắc), cuộc bao vây này kéo dài trong hơn một năm. Khoảng tết năm 619, tướng Tùy trấn thủ thành Bắc Bình là Lý Cảnh (李景) thấy không thể giữ thành lâu thêm nữa, vì thế đã bỏ thành khi một tướng Tùy khác là Đặng Cảo (鄧暠) đem quân đến cứu viện. Cao Khai Đạo đã chiếm được Bắc Bình, sau đó tiếp tục chiếm Ngư Dương (漁陽, nay thuộc Kế, Thiên Tân). Cao Khai Đạo xưng là Yên Vương và cải nguyên niên hiệu là Thủy Hưng, định đô tại Ngư Dương.

Trong khi đó, một thủ lĩnh nổi dậy khác ở gần đó là tăng nhân Cao Đàm Thịnh (高曇晟) đã chiếm lấy Hoài Nhung và xưng là Đại Thừa hoàng đế. Cao Đàm Thịnh phái sứ giả đến chiêu hàng Cao Khai Đạo, Cao Khai Đạo chấp thuận. Cao Đàm Thịnh và Cao Khai Đạo kết làm huynh đệ, Cao Đàm Thịnh phong cho Cao Khai Đạo tước "Tề Vương". Tuy nhiên, vài tháng sau đó, Cao Khai Đạo giết chết Cao Đàm Thịnh, đoạt lấy bộ hạ của người này và rời quốc đô đến Hoài Nhung. Cả Cao Khai Đạo và Đậu Kiến Đức (một thủ lĩnh nổi dậy khác) đều cố tiến công U châu (幽州, nay gần tương ứng với Bắc Kinh) do La Nghệ trấn thủ, La Nghệ cự tuyệt quy hàng song thay vào đó lại quy phục triều Đường.